//
//  Problem646.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/3/8.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 646. 最长数对链 【动态规划】【数组拼接】
 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
 示例：
     输入：[[1,2], [2,3], [3,4]]
     输出：2
     解释：最长的数对链是 [1,2] -> [3,4]
 提示：
    给出数对的个数在 [1, 1000] 范围内。
 */
@objcMembers class Problem646: NSObject {
    func solution() {
        print(findLongestChain([[1,2], [2,3], [3,4], [2,3], [2, 4], [3,4], [4,5], [5,6]]))
        print(findLongestChain([[3,4],[2,3],[1,2]]))
    }
    
    /*
     动态规划
     1: 创建一个数组dp[len]
     2: dp[i] i~end的最长数对链的长度
     3: dp[i] = max()
        for (j in 0..<len) {
            if pairs[i] 符合要求, i != j {
                dp[i] = max(dp[i], 1+dp[j])
            }
        }
     */
    func findLongestChain(_ pairs: [[Int]]) -> Int {
        if pairs.count == 1 {
            return 1
        }
        
        var dp = Array(repeating: -1, count: pairs.count)
        
        var value = 1
        for i in 0..<pairs.count {
            value = max(value, findLongestChain(pairs, &dp, i))
        }
        
        print(dp)
        return value
    }
    
    func findLongestChain(_ pairs: [[Int]], _ dp: inout [Int], _ start: Int) -> Int {
        print("start = \(start)")
        if dp[start] != -1 {
            return dp[start]
        }
        
        for i in 0..<pairs.count {
            if pairs[i][0] > pairs[start][1], i != start {
                dp[start] = max(dp[start], 1 + findLongestChain(pairs, &dp, i))
            }
        }
        
        if dp[start] == -1 {
            dp[start] = 1
        }
        
        return dp[start]
    }
}
